{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Correct a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: correctBinaryTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #纠正二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一棵二叉树，这棵二叉树有个小问题，其中<strong>有且只有一个</strong>无效节点，它的右子节点错误地指向了与其在<strong>同一层</strong>且在其<strong>右侧</strong>的一个其他节点。</p>\n",
    "\n",
    "<p>给定一棵这样的问题二叉树的根节点 <code>root</code> ，将该无效节点<strong>及其所有子节点移除</strong>（除被错误指向的节点外），然后返回新二叉树的根结点。</p>\n",
    "\n",
    "<p><b>自定义测试用例：</b></p>\n",
    "\n",
    "<p>测试用例的输入由三行组成：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>TreeNode root</code></li>\n",
    "\t<li><code>int fromNode</code> （在<strong> </strong><code>correctBinaryTree</code> 中<strong>不可见</strong>）</li>\n",
    "\t<li><code>int toNode</code> （在<strong> </strong><code>correctBinaryTree</code> 中<strong>不可见</strong>）</li>\n",
    "</ul>\n",
    "\n",
    "<p>当以 <code>root</code> 为根的二叉树被解析后，值为 <code>fromNode</code> 的节点 <code>TreeNode</code> 将其右子节点指向值为 <code>toNode</code> 的节点 <code>TreeNode</code> 。然后， <code>root</code> 传入 <code>correctBinaryTree</code> 的参数中。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>示例 1:</b></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/22/ex1v2.png\" style=\"width: 250px; height: 177px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [1,2,3], fromNode = 2, toNode = 3\n",
    "<strong>输出:</strong> [1,null,3]\n",
    "<strong>解释:</strong> 值为 2 的节点是无效的，所以移除之。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/22/ex2v3.png\" style=\"width: 350px; height: 255px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [8,3,1,7,null,9,4,2,null,null,null,5,6], fromNode = 7, toNode = 4\n",
    "<strong>输出:</strong> [8,3,1,null,null,9,4,null,null,5,6]\n",
    "<strong>解释:</strong> 值为 7 的节点是无效的，所以移除这个节点及其子节点 2。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点个数的范围是 <code>[3, 10<sup>4</sup>]</code> 。</li>\n",
    "\t<li><code>-10<sup>9</sup> <= Node.val <= 10<sup>9</sup></code></li>\n",
    "\t<li>所有的 <code>Node.val</code> 都是<strong>互不相同</strong>的。</li>\n",
    "\t<li><code>fromNode != toNode</code></li>\n",
    "\t<li><code>fromNode</code> 和 <code>toNode</code> 将出现在树中的同一层。</li>\n",
    "\t<li><code>toNode</code> 在 <code>fromNode</code> 的右侧。</li>\n",
    "\t<li><code>fromNode.right</code> 在测试用例的树中建立后为 <code>null</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [correct-a-binary-tree](https://leetcode.cn/problems/correct-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [correct-a-binary-tree](https://leetcode.cn/problems/correct-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n2\\n3', '[8,3,1,7,null,9,4,2,null,null,null,5,6]\\n7\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return root\n",
    "\n",
    "        q = [root]\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            visited = set()\n",
    "            for _ in range(size):\n",
    "                cur = q.pop(0)\n",
    "                if cur.right:\n",
    "                    if cur.right.right and cur.right.right.val in visited:\n",
    "                        cur.right = None\n",
    "                        return root\n",
    "                    q.append(cur.right)\n",
    "                    visited.add(cur.right.val)\n",
    "                if cur.left:\n",
    "                    if cur.left.right and cur.left.right.val in visited:\n",
    "                        cur.left = None\n",
    "                        return root\n",
    "                    q.append(cur.left)\n",
    "                    visited.add(cur.left.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\r\n",
    "        # BFS，每一层从右往左，看结点是否重复出现。本层讨论的对象是下一层\r\n",
    "        Q = [root]\r\n",
    "        while Q:\r\n",
    "            cur_len = len(Q)\r\n",
    "            nxt_level = set()\r\n",
    "            for _ in range(cur_len):\r\n",
    "                p = Q.pop(0)\r\n",
    "                if p.right:\r\n",
    "                    if p.right.right in nxt_level:\r\n",
    "                        p.right = None\r\n",
    "                        return root\r\n",
    "                    else:\r\n",
    "                        Q.append(p.right)\r\n",
    "                        nxt_level.add(p.right)\r\n",
    "                if p.left:\r\n",
    "                    if p.left.right in nxt_level:\r\n",
    "                        p.left = None\r\n",
    "                        return root\r\n",
    "                    else:\r\n",
    "                        Q.append(p.left)\r\n",
    "                        nxt_level.add(p.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        queue = [[None, root]]\n",
    "        while queue:\n",
    "            check = set([x[1].val for x in queue])\n",
    "            temp = []\n",
    "            for pre, cur in queue:\n",
    "                if cur.left:    temp.append([cur, cur.left])\n",
    "                if cur.right:\n",
    "                    if cur.right.val in check:\n",
    "                        if pre.left == cur: pre.left = None\n",
    "                        else:   pre.right = None\n",
    "                        return root\n",
    "                    else:\n",
    "                        temp.append([cur, cur.right])\n",
    "            queue = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None \n",
    "\n",
    "        q = [root]\n",
    "\n",
    "        visited = set([])\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                cur = q.pop(0)\n",
    "                if cur.right:\n",
    "                    if cur.right.right and cur.right.right.val in visited:\n",
    "                        cur.right = None \n",
    "                        return root\n",
    "                    q.append(cur.right)\n",
    "                    visited.add(cur.right.val)\n",
    "                if cur.left:\n",
    "                    if cur.left.right and cur.left.right.val in visited:\n",
    "                        cur.left = None \n",
    "                        return root\n",
    "                    q.append(cur.left)\n",
    "                    visited.add(cur.left.val)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        q = deque([[root, None, 'L']])  # node, parent, dir\n",
    "        seen = {root.val}\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                cur, parent, dir = q.popleft()\n",
    "                if cur.right and cur.right.val in seen:  # invalid node\n",
    "                    if dir == 'L':\n",
    "                        parent.left = None\n",
    "                    else:\n",
    "                        parent.right = None\n",
    "                    return root\n",
    "                if cur.left:\n",
    "                    q.append([cur.left, cur, 'L'])\n",
    "                    seen.add(cur.left.val)\n",
    "                if cur.right:\n",
    "                    q.append([cur.right, cur, 'R'])\n",
    "                    seen.add(cur.right.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        queue = [[None, root]]\n",
    "        while queue:\n",
    "            check = set([x[1].val for x in queue])\n",
    "            temp = []\n",
    "            for pre, cur in queue:\n",
    "                if cur.left:    temp.append([cur, cur.left])\n",
    "                if cur.right:\n",
    "                    if cur.right.val in check:\n",
    "                        if pre.left == cur: pre.left = None\n",
    "                        else:   pre.right = None\n",
    "                        return root\n",
    "                    else:\n",
    "                        temp.append([cur, cur.right])\n",
    "            queue = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return root\n",
    "        dq = deque([(root, None, None)])\n",
    "        while dq:\n",
    "            node_set = set()\n",
    "            level_nodes = list()\n",
    "            for _ in range(len(dq)):\n",
    "                tmp, parent, is_left = dq.popleft()\n",
    "                level_nodes.append((tmp, parent, is_left))\n",
    "                node_set.add(tmp)\n",
    "            is_break = False\n",
    "            for node, parent, is_left in level_nodes:\n",
    "                if node.left:\n",
    "                    dq.append((node.left, node, True))\n",
    "                if node.right:\n",
    "                    if node.right in node_set:\n",
    "                        if is_left:\n",
    "                            parent.left = None\n",
    "                        else:\n",
    "                            parent.right = None\n",
    "                        is_break = True\n",
    "                        break\n",
    "                    else:\n",
    "                        dq.append((node.right, node, False))\n",
    "            if is_break:\n",
    "                break\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        queue = [root]\n",
    "        new = root\n",
    "        while queue:\n",
    "            queue2 = []\n",
    "            index = set()\n",
    "            for root in queue:\n",
    "                if root.right:\n",
    "                    if root.right.right in index:\n",
    "                        root.right = None\n",
    "                        return new\n",
    "                    queue2.append(root.right)\n",
    "                    index.add(root.right)\n",
    "                if root.left:\n",
    "                    if root.left.right in index:\n",
    "                        root.left = None\n",
    "                        return new\n",
    "                    queue2.append(root.left)\n",
    "                    index.add(root.left)\n",
    "            queue = queue2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()   \n",
    "                if node.right:\n",
    "                    if not (node.right.right and node.right.right in queue):  \n",
    "                        queue.append(node.right)\n",
    "                    else:\n",
    "                        node.right = None\n",
    "                        return root\n",
    "                        \n",
    "                if node.left:\n",
    "                    if not (node.left.right and node.left.right in queue):\n",
    "                        queue.append(node.left)\n",
    "                    else:\n",
    "                        node.left = None\n",
    "                        return root\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        q = [root]\n",
    "        while q:\n",
    "            nq = []\n",
    "            parent = dict()\n",
    "            for x in q:\n",
    "                if x.left:\n",
    "                    parent[x.left] = x\n",
    "                    nq.append(x.left)\n",
    "                if x.right:\n",
    "                    parent[x.right] = x\n",
    "                    nq.append(x.right)\n",
    "            \n",
    "            dic = set(nq)\n",
    "            for x in nq:\n",
    "                if x.right in dic:\n",
    "                    if parent[x].left == x:\n",
    "                        parent[x].left = None\n",
    "                    else:\n",
    "                        parent[x].right = None\n",
    "                    return root\n",
    "            q = nq\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        q = [root]\n",
    "        while q:\n",
    "            cur_len = len(q)\n",
    "            nxt_level = set()\n",
    "            for _ in range(cur_len):\n",
    "                p = q.pop(0)\n",
    "                if p.right:\n",
    "                    if p.right.right in nxt_level:\n",
    "                        p.right = None \n",
    "                        return root \n",
    "                    else:\n",
    "                        q.append(p.right)\n",
    "                        nxt_level.add(p.right)\n",
    "                if p.left:\n",
    "                    if p.left.right in nxt_level:\n",
    "                        p.left = None\n",
    "                        return root\n",
    "                    else:\n",
    "                        q.append(p.left)\n",
    "                        nxt_level.add(p.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        # define a queue to store nodes in each level\n",
    "        q = deque()\n",
    "        #initialize queue\n",
    "        q.append(root)\n",
    "\n",
    "        while q:\n",
    "            level = []\n",
    "\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "\n",
    "                if cur.right:\n",
    "                    if cur.right.right in level:\n",
    "                        cur.right = None\n",
    "                        return root\n",
    "                    q.append(cur.right)\n",
    "                    level.append(cur.right)\n",
    "\n",
    "                if cur.left:\n",
    "                    if cur.left.right in level:\n",
    "                        cur.left = None\n",
    "                        return root\n",
    "                    q.append(cur.left)\n",
    "                    level.append(cur.left)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None \n",
    "\n",
    "        q = [root]\n",
    "\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            visited = set([])\n",
    "            for _ in range(size):\n",
    "                cur = q.pop(0)\n",
    "                if cur.right:\n",
    "                    if cur.right.right and cur.right.right.val in visited:\n",
    "                        cur.right = None \n",
    "                        return root\n",
    "                    q.append(cur.right)\n",
    "                    visited.add(cur.right.val)\n",
    "                if cur.left:\n",
    "                    if cur.left.right and cur.left.right.val in visited:\n",
    "                        cur.left = None \n",
    "                        return root\n",
    "                    q.append(cur.left)\n",
    "                    visited.add(cur.left.val)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = set([])\n",
    "\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None \n",
    "\n",
    "        if root.right and root.right.val in self.visited:\n",
    "            return None \n",
    "\n",
    "        self.visited.add(root.val)\n",
    "\n",
    "        root.right = self.correctBinaryTree(root.right)\n",
    "        root.left = self.correctBinaryTree(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        s=set()\n",
    "        def dfs(cur,fa):\n",
    "            if cur==None:\n",
    "                return\n",
    "            if cur.right!=None and cur.right.val in s:\n",
    "                if fa.left==cur:\n",
    "                    fa.left=None\n",
    "                else:\n",
    "                    fa.right=None\n",
    "                return\n",
    "            s.add(cur.val)\n",
    "            dfs(cur.right,cur)\n",
    "            dfs(cur.left,cur)\n",
    "        dfs(root,root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        h = set()\n",
    "        def dfs(root):\n",
    "            if not root: return None\n",
    "            nonlocal h\n",
    "            if root.right and root.right.val in h:\n",
    "                return None\n",
    "\n",
    "            h.add(root.val)\n",
    "            root.right = dfs(root.right)\n",
    "            root.left = dfs(root.left)\n",
    "            return root\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        h = set()\n",
    "        def dfs(root):\n",
    "            if not root: return None\n",
    "            nonlocal h\n",
    "            if root.right and root.right.val in h:\n",
    "                return None\n",
    "\n",
    "            h.add(root.val)\n",
    "            root.right = dfs(root.right)\n",
    "            root.left = dfs(root.left)\n",
    "            return root\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    visited = set()\n",
    "\n",
    "    def correctBinaryTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        if root.right is not None and root.right in self.visited:\n",
    "            return None\n",
    "        \n",
    "        self.visited.add(root)\n",
    "        root.right = self.correctBinaryTree(root.right)\n",
    "        root.left = self.correctBinaryTree(root.left)\n",
    "        return root\n",
    "    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
